\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
% \usepackage[backend=bibtex,style=numeric]{biblatex}
\usepackage[UTF8]{ctex}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{tikz}

\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\begin{document}
% ==================================================
\title{NA项目作业：设计与数学文档}

\author{金郁香 3220103054
  \thanks{电子邮箱: \texttt{2621201771@qq.com}}}
\affil{浙江大学 信计2201班}

\date{截止时间: \today}

\maketitle

% ============================================

\section*{I. 程序结构说明}
这一部分主要介绍本项目包含的所有程序和文件之间的整体结构。项目目录结构如下：

\begin{itemize}
    \item 根目录包含整个项目的文件和子目录。
    \item \texttt{src/} 目录存放源代码文件，包括算法实现和库文件。其中\texttt{solve/}内包含对每个问题分别求解的\texttt{.cpp} 文件，\texttt{Eigen/} 存放外部库文件。
    \item \texttt{doc/} 目录包含设计文档和报告的 \texttt{.tex} 文件，用于编译生成 \texttt{.pdf} 文件。
    \item \texttt{figure/} 目录存放文档中使用的所有图片文件。
    \item \texttt{makefile} 用于构建项目。
\end{itemize}

\begin{center}
    \begin{tikzpicture}
        \node {SplineProject}[grow'=right, scale=0.6, % 缩小整个树状图
        level distance=3cm, % 增加层间距
        sibling distance=1.5cm, % 减小节点间距
        level 1/.style={level distance=6cm, sibling distance=2cm},
        level 2/.style={level distance=7.5cm, sibling distance=1cm}]
        child {node {doc/}
            child {node {design.tex}
            }
            child [missing] {}
            child {node {report.tex}
            }
        }
        child [missing] {}    
        child {node {makefile}}    %child [missing] {}充当间隔符号，隔开各个子树，可以增减其个数调整子树间距。
        child [missing] {}
        child {node {figure/}}    
        child [missing] {}        
        child { node {src/}
            child {node {solve/}
            }
            child [missing] {}
            child {node {spline\_functions.h}
            }
            child [missing] {}
            child {node {Curvefitting.h}
            }
            child [missing] {}
            child {node {Function.hpp}
            }
            child [missing] {}
            child {node {Eigen/}
            }
        };
    \end{tikzpicture}
\end{center}


\section*{II. 主要设计思路} 
这一部分主要介绍本项目的主体部分——几个头文件的设计思路。

\subsection*{II-a. Function.hpp}
\texttt{Function.hpp} 定义了二维和三维空间中向量值函数的基本结构和操作。该文件使用面向对象的编程方法，提供了函数评估和导数计算的基础接口。

\subsubsection*{A. 类定义}
\subparagraph*{Function 类}
\texttt{Function} 是一个抽象基类，定义了二维函数的基本操作。它包含两个纯虚函数：
\begin{itemize}
    \item $\texttt{virtual dot operator() (double x) const = 0;}$ 用于计算函数在给定点 $x$ 的值。
    \item $\texttt{virtual dot derivative(double x) const = 0;}$ 用于计算函数在点 $x$ 的导数值。
\end{itemize}

\subparagraph*{Function\_3 类}
\texttt{Function\_3} 类也是一个抽象基类，用于三维空间中的函数。它定义了一个纯虚函数：
\begin{itemize}
    \item $\texttt{virtual dot\_3 operator() (double x) const = 0;}$ 用于计算三维向量值函数在给定点 $x$ 的值，返回一个 \texttt{dot\_3} 结构，表示三维空间中的一个点。
\end{itemize}

\subsubsection*{B. 数据结构定义}
\subparagraph*{dot 结构体}
\texttt{dot} 结构体用于存储二维空间中的一个点，包含两个 \texttt{double} 类型的成员变量 \texttt{x} 和 \texttt{y}。

\subparagraph*{dot\_3 结构体}
\texttt{dot\_3} 结构用于存储三维空间中的一个点，包含三个 \texttt{double} 类型的成员变量 \texttt{x}、\texttt{y} 和 \texttt{z}。

\subsection*{II-b. spline\_functions.h}
\texttt{spline\_functions.h} 是样条函数库的核心头文件，提供了一个灵活且功能丰富的样条函数库，它定义了多种样条函数类，每个类对应一种特定的样条函数类型，从而实现对样条函数的多样化支持。

\subsubsection*{A. 类之间的关系 }

类之间的关系主要是继承关系。例如，\texttt{LinearSpline\_p} 和 \texttt{PeriodicCubicSpline\_p} 都继承自PP形式基类 \texttt{PPFormSpline}， \texttt{LinearSpline\_B} 和 \texttt{ArbitraryOrderBSpline} 都继承自B样条基类 \texttt{BSpline}，而 \texttt{PPFormSpline} 和 \texttt{BSpline} 都继承自抽象基类 \texttt{SplineFunction}。

下面用一个树状图来详细展示所有类之间的继承关系。
\begin{center}
    \begin{tikzpicture}
        \node {SplineFunction}[grow'=right, scale=0.6, % 缩小整个树状图
        level distance=3cm, % 增加层间距
        sibling distance=1.5cm, % 减小节点间距
        level 1/.style={level distance=6cm, sibling distance=2cm},
        level 2/.style={level distance=7.5cm, sibling distance=1cm}]
        child {node {PPFormSpline}
            child {node {LinearSpline\_p}
            }
            child [missing] {}
            child {node {PeriodicCubicSpline\_p}
            }
            child [missing] {}
            child {node {NaturalSpline\_p}
            }
            child [missing] {}
            child {node {ClampedCubicSpline\_p}
            }
        }    
        child [missing] {}    %child [missing] {}充当间隔符号，隔开各个子树，可以增减其个数调整子树间距。
        child [missing] {}
        child [missing] {}    
        child [missing] {}        
        child { node {BSpline}
            child {node {LinearSpline\_B}
            }
            child [missing] {}
            child {node {QuadraticSpline\_B}
            }
            child [missing] {}
            child {node {PeriodicCubicSpline\_B}
            }
            child [missing] {}
            child {node {NaturalSpline\_B}
            }
            child [missing] {}
            child {node {ClampedCubicSpline\_B}
            }
            child [missing] {}
            child {node {ArbitraryOrderBSpline}
            }
        };
    \end{tikzpicture}
\end{center}

\subsubsection*{B. 类的功能接口}

每个类都实现了 \texttt{SplineFunction} 规范的接口，提供了 \texttt{evaluate} 方法，用于计算样条函数的值。此外，每个类还可能包含特定的成员函数，用于处理该类样条函数的特定计算，例如三次B样条函数类下的\texttt{Nip\_3}成员函数，用于返回B样条的三次基函数在给定分段给定x处的函数值。

\subsubsection*{C. 三个基类定义}

\subparagraph*{SplineFunction 类}
\texttt{SplineFunction} 是一个抽象基类，定义了所有样条函数的基础操作，规范了功能接口。它包含两个纯虚函数：
\begin{itemize}
    \item $\texttt{virtual ~SplineFunction();}$ 用于析构样条函数对象。
    \item $\texttt{virtual double evaluate(double x) const = 0;}$ 用于计算样条函数在点 $x$ 的函数值。
\end{itemize}

\subparagraph*{PPFormSpline 类}
\texttt{PPFormSpline} 类继承自 \texttt{SplineFunction}，表示 pp 形式的样条函数基类，它增加了两个成员变量：
\begin{itemize}
    \item $\texttt{std::vector<double> knots;}$ 构建样条函数所需的节点$x_i$。
    \item $\texttt{std::vector<double> coefficients;}$ 构建样条函数所需的节点处的函数值$f(x_i)$。
\end{itemize}
\subparagraph*{BSpline 类}
\texttt{BSpline} 类同样继承自 \texttt{SplineFunction}，表示 B 样条函数基类，它增加了三个成员变量：
\begin{itemize}
    \item $\texttt{std::vector<double> knots;}$ 构建样条函数所需的节点$t_i$。
    \item $\texttt{std::vector<double> coefficients;}$ 构建样条函数所需的相关系数，一般为节点处的函数值$f(t_i)$。
    \item $\texttt{int degree;}$ B样条函数的阶数$n$。
\end{itemize}

\subsubsection*{D. 核心类定义}

\subparagraph*{LinearSpline\_p 类}
\texttt{LinearSpline\_p} 类继承自 \texttt{PPFormSpline}，表示 pp 形式的线性样条函数类，并重写了评估函数：
\begin{itemize}
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：对 $x\in[x_i,x_{i+1}]$，计算线性插值公式 $s(x) = f_{i}+\frac{f_{i+1}-f_i}{t_{i+1}-x_i}\cdot(x-t_i)$ 即可。
\end{itemize}

\subparagraph*{LinearSpline\_B 类}
\texttt{LinearSpline\_B} 类继承自 \texttt{BSpline}，表示线性 B 样条函数类，并重写了评估函数：
\begin{itemize}
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：根据线性B样条基函数只在一个节点处取值为$1$，其余节点处均为$0$的性质可直接推得，每个$B_i^1$的系数就等于$f(t_i)$，所以对 $x\in[t_i,t_{i+1}]$，计算求和公式 $s(x) = f_{i}\cdot\frac{t_{i+1}-x}{t_{i+1}-t_i}+f_{i+1}\cdot\frac{x-t_{i}}{t_{i+1}-t_i}$ 即可。
\end{itemize}

\subparagraph*{ClampedCubicSpline\_p 类}
\texttt{ClampedCubicSpline\_p} 类继承自 \texttt{PPFormSpline}，表示 pp 形式的完全三次样条函数类，增加了两个成员变量并重写了评估函数：
\begin{itemize}
    \item $\texttt{double m1;}$; 第一个节点处的一阶导数。
    \item $\texttt{double mN;}$; 最后一个节点处的一阶导数。
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 根据以下公式计算 $\mu_i$ 和 $\lambda_i$，
        \[\mu_{i} = \frac{x_{i} - x_{i-1}}{x_{i+1} - x_{i-1}}, \quad \lambda_{i} = \frac{x_{i+1} - x_{i}}{x_{i+1} - x_{i-1}}.\]
        并利用以下推导得到的等式关系，
        \[\lambda_i m_{i-1} + 2m_i + \mu_i m_{i+1} = 3\mu_i f[x_i, x_{i+1}] + 3\lambda_i f[x_{i-1}, x_i].\]
        构建三对角矩阵 A 和 向量 b，以表达如下线性方程组 Ax = b，其中$m_1 = m1,\quad m_N = mN,\quad x = [m_2,m_3,\dots,m_{N-1}]^T$。
        \begin{align*}
            &
            \begin{bmatrix}
                2 & \mu_2 & & & & \\
                \lambda_3 & 2 & \mu_3 & & &\\
                & \ddots & \ddots & \ddots & &\\
                & &\lambda_i & 2 & \mu_i & &\\
                & & & \ddots & \ddots & \ddots \\
                & & & & \lambda_{N-2} & 2 & \mu_{N-2} \\
                & & & & & \lambda_{N-1} & 2
            \end{bmatrix}
            \begin{bmatrix}
                m_2 \\
                m_3 \\
                \vdots \\
                m_i \\
                \vdots \\
                m_{N-2} \\
                m_{N-1}
            \end{bmatrix}
            = b, \\
            & b= 
            \begin{bmatrix}
                3\mu_2 f[x_2,x_3]+3\lambda_2 f[x_1,x_2]-\lambda_2 m_1 \\
                3\mu_3 f[x_3,x_4]+3\lambda_3 f[x_2,x_3] \\
                \vdots \\
                3\mu_i f[x_i,x_{i+1}]+3\lambda_i f[x_{i-1},x_i] \\
                \vdots \\
                3\mu_{N-2} f[x_{N-2},x_{N-1}]+3\lambda_{N-2} f[x_{N-3},x_{N-2}] \\
                3\mu_{N-1} f[x_{N-1},x_{N}]+3\lambda_{N-1} f[x_{N-2},x_{N-1}]-\mu_{N-1}m_N
            \end{bmatrix}
        \end{align*}
        \item 使用 Eigen 库的稀疏矩阵求解器解线性方程组 Ax = b，得到一阶导数向量。
        \item 对于给定的 $x\in[t_i,t_{i+1}]$，计算如下三次牛顿插值公式并输出。
         \[s(x) = f_i + (x - x_i)m_i + (x - x_i)^2 \frac{f[x_i,x_{i+1}] - m_i}{x_{i+1} - x_i} + (x - x_i)^2(x - x_{i+1}) \frac{m_i + m_{i+1} - 2f[x_i,x_{i+1}]}{(x_{i+1} - x_i)^2}.\]
    \end{enumerate}
\end{itemize}

\subparagraph*{NaturalSpline\_p 类}
\texttt{NaturalSpline\_p} 类继承自 \texttt{PPFormSpline}，表示 pp 形式的自然三次样条函数类，并重写了评估函数：
\begin{itemize}
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 初始化二阶导数向量 $M$，其中 $M_0 = M_{N-1} = 0$，表示自然边界条件。
        \item 根据之前的公式计算 $\mu_i$ 和 $\lambda_i$，
        并利用以下推导得到的等式关系，
        \[\mu_i M_{i-1} + 2M_i + \lambda_i M_{i+1} = 6f[x_{i-1}, x_i, x_{i+1}].\]
        构建三对角矩阵 A 和 向量 b，以表达如下线性方程组 Ax = b，其中 $x = [M_2, M_3, \dots, M_{N-2}]^T$。
        \begin{align*}
            \scriptstyle
            \begin{bmatrix}
                2 & \lambda_2 & & & &\\
                \mu_3 & 2 & \lambda_3 & & &\\
                & \ddots & \ddots & \ddots & &\\
                & & \mu_i & 2 & \lambda_i & &\\
                & & & \ddots & \ddots & \ddots \\
                & & & & \mu_{N-2} & 2 & \lambda_{N-2} \\
                & & & & & \mu_{N-1} & 2
            \end{bmatrix}
            \begin{bmatrix}
                M_2 \\
                M_3 \\
                \vdots \\
                M_i \\
                \vdots \\
                M_{N-2} \\
                M_{N-1}
            \end{bmatrix}
            =
            \begin{bmatrix}
                6f[x_1,x_2,x_3]-\mu_2 M_1 \\
                6f[x_2,x_3,x_4] \\
                \vdots \\
                6f[x_{i-1},x_i,x_{i+1}] \\
                \vdots \\
                6f[x_{N-3},x_{N-2},x_{N-1}] \\
                6f[x_{N-2},x_{N-1},x_{N}]-\lambda_{N-1}M_N
            \end{bmatrix}
        \end{align*}
        \item 使用 Eigen 库的稀疏矩阵求解器解线性方程组 Ax = b，得到二阶导数向量。
        \item 对于给定的 $x\in[t_i,t_{i+1}]$，计算如下三次牛顿插值公式并输出。
        \[m_i = f[x_i,x_{i+1}]-\frac{1}{6}(M_{i+1}+2M_i)(x_{i+1}-x_i),\]
        \[m_{i+1} = f[x_i,x_{i+1}]-\frac{1}{6}(M_{i}+2M_{i+1})(x_{i}-x_{i+1}),\]
        \[s(x) = f_i + (x - x_i)m_i + (x - x_i)^2 \frac{f[x_i,x_{i+1}] - m_i}{x_{i+1} - x_i} + (x - x_i)^2(x - x_{i+1}) \frac{m_i + m_{i+1} - 2f[x_i,x_{i+1}]}{(x_{i+1} - x_i)^2}\]
    \end{enumerate}
\end{itemize}

\subparagraph*{PeriodicCubicSpline\_p 类}
\texttt{PeriodicCubicSpline\_p} 类继承自 \texttt{PPFormSpline}，表示 pp 形式的周期三次样条函数类，并重写了评估函数：
\begin{itemize}
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于1，并且系数数量与节点数量相等。
        \item 与 NaturalSpline\_p 类中的 evaluate 函数一样，以二阶导数为未知量构建线性方程组 Ax = b并求解。考虑到周期边界条件，我们额外得到了以下两个等式：
        \[M_1 = M_N,\]
        \[m_1 = m_N \Rightarrow f[x_1,x_2]-\frac{1}{6}(M_2+2M_1)(x_2-x_1) = f[x_{N-1},x_{N}]-\frac{1}{6}(M_{n-2}+2M_N)(x_{N-1}-x_N).\]
        因此得到如下线性方程组 Ax = b ：
        \begin{align*}
            \scriptscriptstyle
            \begin{bmatrix}
                1 & & & & & -1\\
                \mu_2 & 2 & \lambda_2 & & \\
                & \ddots & \ddots & \ddots & \\
                & & \mu_i & 2 & \lambda_i & \\
                & & & \ddots & \ddots & \ddots \\
                & & & \mu_{N-1} & 2 & \lambda_{N-1} \\
                2(x_2-x_1)& x_2-x_1 & & & x_N-x_{N-1} & 2(x_N-x_{N-1})
            \end{bmatrix}
            \begin{bmatrix}
                M_1 \\
                M_2 \\
                \vdots \\
                M_i \\
                \vdots \\
                M_{N-1} \\
                M_{N}
            \end{bmatrix}
            =
            \begin{bmatrix}
                0 \\
                6f[x_1,x_2,x_3] \\
                \vdots \\
                6f[x_{i-1},x_i,x_{i+1}] \\
                \vdots \\
                6f[x_{N-2},x_{N-1},x_{N}] \\
                6f[x_1,x_2]-6f[x_{N-1},x_N]
            \end{bmatrix}
        \end{align*}
        \item 与 NaturalSpline\_p 类中的 evaluate 函数一样，使用 Eigen 库的稀疏矩阵求解器解线性方程组 Ax = b，得到二阶导数向量；对于给定的 $x\in[t_i,t_{i+1}]$，计算三次牛顿插值公式并输出。
    \end{enumerate}
\end{itemize}


\subparagraph*{QuadraticSpline\_B 类}
\texttt{QuadraticSpline\_B} 类继承自 \texttt{BSpline}，表示二次B样条函数类，增加了一个成员函数并重写了评估函数：
\begin{itemize}
    \item $\texttt{double Nip\_2(int i, double x0) const}$; 计算B样条的二次基函数在给定分段给定x处的函数值（这里只考虑均匀节点）。
    \newline
    算法流程：注意到这里基函数的节点i和二次B样条构建时输入的节点i存在0.5的偏差，所以首先令$x = x0 + 0.5$，再按照以下定义返回函数值$B_i^2(x)$。
    \[
    B_i^2(x) =
    \begin{cases} 
    \frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})}, & x \in (t_{i-1}, t_i]; \\
    \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)} + \frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_i)(t_{i+1}-t_i)}, & x \in (t_i, t_{i+1}]; \\
    \frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}, & x \in (t_{i+1}, t_{i+2}]; \\
    error, & \text{otherwise}.
    \end{cases}
    \]
    另外，由于计算时需要用到的$t_i$可能超出给定的knots中的节点范围，这里人为地用以1为间隔的均匀节点将knots向两端延拓：
    \[
    \begin{cases}
        t_i = t_1 + (i - 1), & i < 1; \\
        t_i = t_N + (i - N), & i > N.
    \end{cases}
    \]
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 与 pp形式样条类中的 evaluate 函数一样，尝试构建线性方程组 Ax = b并求解。这里以$S(x) = \sum_{i = 0}^{N} a_i B_{i,\mathbb{Z}}^2(x)$中每个基函数的系数$a_i$为未知量，利用$S(t_i) = f(t_i)$得到以下等式：
        \[a_{i-1}+6a_i+a_{i+1}=8f(t_i), \quad i\in[2,3,\dots,N-2]\]
        在两个端点处，我们由$S(t_1-0.5)=f(t_1-0.5)$和$S(t_N-0.5)=f(t_N-0.5)$得到：
        \[a_0 = 2f(t_1-\frac{1}{2}) - a_1, \quad a_N = 2f(t_{N-1}+\frac{1}{2}) - a_{N-1}.\]
        因此得到如下线性方程组 Ax = b ：
        \begin{align*}
            \begin{bmatrix}
                5 & 1 & & & & \\
                1 & 6 & 1 & & &\\
                & \ddots & \ddots & \ddots & &\\
                & & 1 & 6 & 1 & &\\
                & & & \ddots & \ddots & \ddots \\
                & & & & 1 & 6 & 1 \\
                & & & & & 1 & 5
            \end{bmatrix}
            \begin{bmatrix}
                a_1 \\
                a_2 \\
                \vdots \\
                a_i \\
                \vdots \\
                a_{N-2} \\
                a_{N-1}
            \end{bmatrix}
            =
            \begin{bmatrix}
                8f(t_1)-2f(t_1-\frac{1}{2}) \\
                8f(t_2) \\
                \vdots \\
                8f(t_i) \\
                \vdots \\
                8f(t_{N-2}) \\
                8f(t_{N-1})-2f(t_{N-1}+\frac{1}{2})
            \end{bmatrix}
        \end{align*}
        \item 同上，使用 Eigen 库的稀疏矩阵求解器解线性方程组 Ax = b，得到二次B样条基函数的系数向量。
        \item 对于给定的 $x\in[t_i-\frac{1}{2},t_i+\frac{1}{2}]$，计算求和公式并输出。
        \[
        s(x) = a_{i-1}B_{i-1,\mathbb{Z}}^2(x)+a_{i}B_{i,\mathbb{Z}}^2(x)+a_{i+1}B_{i+1,\mathbb{Z}}^2(x).
        \]
        其中$B_{i,\mathbb{Z}}^2(x)$调用成员函数$Nip\_2(i,x)$得到。
    \end{enumerate}
\end{itemize}

\subparagraph*{ClampedCubicSpline\_B 类}
\texttt{ClampedCubicSpline\_B} 类继承自 \texttt{BSpline}，表示完全三次B样条函数类，增加了两个成员变量、一个成员函数并重写了评估函数：
\begin{itemize}
    \item $\texttt{double m1;}$; 第一个节点处的一阶导数。
    \item $\texttt{double mN;}$; 最后一个节点处的一阶导数。
    \item $\texttt{double Nip\_3(int i, double x) const}$; 计算B样条的三次基函数在给定分段给定x处的函数值。
    \newline
    算法流程：按照以下定义返回函数值$B_i^3(x)$，其中，超出范围的节点同上进行人为延拓。
\end{itemize}
    \[
    B_i^3(x) =\\
    \begin{cases} 
    \frac{(x-t_{i-1})^3}{(t_{i+2}-t_{i-1})(t_{i+1}-t_{i-1})(t_i-t_{i-1})}, & x \in (t_{i-1}, t_i]; \\
    \frac{x-t_{i-1}}{t_{i+2}-t_{i-1}}\cdot\left[\frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)} + \frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_i)(t_{i+1}-t_i)}\right]+\frac{t_{i+3}-x}{t_{i+3}-t_i}\cdot\frac{(x-t_i)^2}{(t_{i+2}-t_i)(t_{i+1}-t_i)}, & x \in (t_i, t_{i+1}]; \\
    \frac{x-t_{i-1}}{t_{i+2}-t_{i-1}}\cdot\frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}+\frac{t_{i+3}-x}{t_{i+3}-t_i}\cdot \left[\frac{(x-t_{i})(t_{i+2}-x)}{(t_{i+2}-t_{i})(t_{i+2}-t_{i+1})} + \frac{(t_{i+3}-x)(x-t_{i+1})}{(t_{i+3}-t_{i+1})(t_{i+2}-t_{i+1})}\right], & x \in (t_{i+1}, t_{i+2}]; \\
    \frac{(t_{i+3}-x)^3}{(t_{i+3}-t_{i+2})(t_{i+3}-t_{i+})(t_{i+3}-t_{i})}, & x \in (t_{i+2}, t_{i+3}]; \\
    error, & \text{otherwise}.
    \end{cases}
    \]
\begin{itemize}
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 与二次B样条函数类的 evaluate 函数一样，尝试构建线性方程组 Ax = b并求解，以$S(x) = \sum_{i = 0}^{N} a_i B_{i,\mathbb{Z}}^2(x)$中每个基函数的系数$a_i$为未知量，利用$S(t_i) = f(t_i)$得到以下等式：
        \[a_{i-2}B_{i-2,\mathbb{Z}}^3(t_i)+a_{i-1}B_{i-1,\mathbb{Z}}^3(t_i)+a_{i}B_{i,\mathbb{Z}}^3(t_i)=f(t_i), \quad i\in[1,2,\dots,N]\]
        在两个端点处，我们结合Nip\_3中的节点延拓原则与完全边界条件$S'(t_1)=m1$和$S'(t_N) = mN$得到：
        \[c_1 = \frac{t_2-t_1+2}{(t_2-t_1)(t_3-t_1+1)},\quad c_0 = 1-c_1,\quad c_2 =\frac{(t_2-t_1+2)(t_2-t_1+1)}{3(t_2-t_1)};\]
        \[\Rightarrow a_{-1} = a_0\cdot c_0+a_1\cdot c_1-m1\cdot c_2.\]
        \[d_1 = \frac{t_N-t_{N-1}+2}{(t_N-t_{N-2}+1)(t_N-t_{N-1})}, \quad d_0 = 1-d_1, \quad d_2 = \frac{(t_N-t_{N-1}+2)(t_N-t_{N-1}+1)}{3(t_N-t_{N-1})};\]
        \[\Rightarrow a_{N} = a_{N-1}\cdot d_0+a_{N-2}\cdot d_1+mN\cdot d_2.\]
        因此得到如下线性方程组 Ax = b ：
        \begin{align*}
            &A =
            \begin{bmatrix}
                A_{1,1} & A_{1,2} & & & & \\
                B_{0,\mathbb{Z}}^3(t_2) & B_{1,\mathbb{Z}}^3(t_2) & B_{2,\mathbb{Z}}^3(t_2) & & &\\
                & \ddots & \ddots & \ddots & &\\
                & & B_{i-2,\mathbb{Z}}^3(t_i) & B_{i-1,\mathbb{Z}}^3(t_i) & B_{i,\mathbb{Z}}^3(t_i) & &\\
                & & & \ddots & \ddots & \ddots \\
                & & & & B_{N-3,\mathbb{Z}}^3(t_{N-1}) & B_{N-2,\mathbb{Z}}^3(t_{N-1}) & B_{N-1,\mathbb{Z}}^3(t_{N-1}) \\
                & & & & & A_{N,N-1} & A_{N,N}
            \end{bmatrix}
            \\
            &\text{其中：}
            \left\{
                \begin{aligned}
                A_{1,1} &= B_{0, \mathbb{Z}}^3(t_1) + c_0 \cdot B_{-1, \mathbb{Z}}^3(t_1), \\
                A_{1,2} &= B_{1, \mathbb{Z}}^3(t_1) + c_1 \cdot B_{-1, \mathbb{Z}}^3(t_1), \\
                A_{N,N-1} &= B_{N-2,\mathbb{Z}}^3(t_N) + d_1 \cdot B_{N,\mathbb{Z}}^3(t_N), \\
                A_{N,N} &= B_{N-1,\mathbb{Z}}^3(t_N) + d_0 \cdot B_{N,\mathbb{Z}}^3(t_N).
                \end{aligned}
            \right. 
            \\
            \\&x =
            \begin{bmatrix}
                a_0 \\
                a_1 \\
                \vdots \\
                a_i \\
                \vdots \\
                a_{N-2} \\
                a_{N-1}
            \end{bmatrix}
            ,\quad b =
            \begin{bmatrix}
                f(t_1)+c_2\cdot m1\cdot B_{-1, \mathbb{Z}}^3(t_1) \\
                f(t_2) \\
                \vdots \\
                f(t_{i+1}) \\
                \vdots \\
                f(t_{N-1}) \\
                f(t_N)-d_2\cdot mN \cdot B_{N, \mathbb{Z}}^3(t_N)
            \end{bmatrix}
        \end{align*}
        \item 同上，使用 Eigen 库的稀疏矩阵求解器解线性方程组 Ax = b，得到三次B样条基函数的系数向量。
        \item 对于给定的 $x\in[t_i,t_{i+1}]$，计算求和公式并输出。
        \[
        s(x) = a_{i-2}B_{i-2,\mathbb{Z}}^3(x)+ a_{i-1}B_{i-1,\mathbb{Z}}^3(x)+a_{i}B_{i,\mathbb{Z}}^3(x)+a_{i+1}B_{i+1,\mathbb{Z}}^3(x).
        \]
        其中$B_{i,\mathbb{Z}}^3(x)$调用成员函数$Nip\_3(i,x)$得到。
    \end{enumerate}
\end{itemize}

\subparagraph*{NaturalSpline\_B 类}
\texttt{NaturalSpline\_B} 类继承自 \texttt{BSpline}，表示自然三次B样条函数类，增加了一个成员函数并重写了评估函数：
\begin{itemize}
    \item $\texttt{double Nip\_3(int i, double x) const}$; 同上。
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 与完全三次B样条函数类的 evaluate 函数基本一样，但在两个端点处，我们结合Nip\_3中的节点延拓原则与自然边界条件$S^"(t_1)=S^"(t_N) = 0$得到：
        \[c_1 = -\frac{t_2-t_1+2}{t_3-t_1+1},\quad c_0 = 1-c_1;\]
        \[\Rightarrow a_{-1} = a_0\cdot c_0+a_1\cdot c_1.\]
        \[d_1 = -\frac{t_N-t_{N-1}+2}{t_N-t_{N-2}+1}, \quad d_0 = 1-d_1;\]
        \[\Rightarrow a_{N} = a_{N-1}\cdot d_0+a_{N-2}\cdot d_1.\]
        同样得到线性方程组 Ax = b, 其中A（但$c_0,c_1,d_0,d_1$更新了）和x形式同上不变，b变化为：
        \begin{align*}
            b =
            \begin{bmatrix}
                f(t_1) \\
                f(t_2) \\
                \vdots \\
                f(t_{i+1}) \\
                \vdots \\
                f(t_{N-1}) \\
                f(t_N)
            \end{bmatrix}
        \end{align*}
        \item 之后均同上。
    \end{enumerate}
\end{itemize}

\subparagraph*{PeriodicCubicSpline\_B 类}
\texttt{PeriodicCubicSpline\_B} 类继承自 \texttt{BSpline}，表示周期三次B样条函数类，增加了一个成员函数并重写了评估函数：
\begin{itemize}
    \item $\texttt{double Nip\_3(int i, double x) const}$; 同上。
    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量与节点数量相等。
        \item 同上，尝试构建线性方程组 Ax = b并求解。但这里我们结合Nip\_3中的节点延拓原则与周期边界条件$S(t_1)=S(t_N)$，$S'(t_1)=S'(t_N)$和$S^"(t_1) = S^"(t_N)$得到：
        \begin{align*}
            \left\{
                \begin{aligned}
                    c_{-1} &= -\frac{t_2-t_1}{(t_2-t_1+2)(t_2-t_1+1)},\, c_1 = \frac{1}{(t_3-t_1+1)(t_2-t_1+1)},\, c_0 =-c_{-1}-c_1; \\
                    d_{-1} &= -\frac{1}{(t_{N}-t_{N-2}+1)(t_{N}-t_{N-1}+1)},\, d_1 = \frac{t_{N}-t_{N-1}}{(t_{N}-t_{N-1}+2)(t_{N}-t_{N-1}+1)},\, d_0 =-d_{-1}-d_1.
                \end{aligned}
            \right.\\
            \Rightarrow 3(c_{-1}\cdot a_{-1}+c_{0}\cdot a_{0}+c_{1}\cdot a_{1})=S'(t_1)=S'(t_N)=3(d_{-1}\cdot a_{N-2}+d_{0}\cdot a_{N-1}+d_{1}\cdot a_{N}).
        \end{align*}
        \begin{align*}
            \left\{
                \begin{aligned}
                    e_{-1} &= \frac{1}{(t_2-t_1+2)(t_2-t_1+1)}, \, e_{1} = \frac{1}{(t_3-t_1+1)(t_2-t_1+1)}, \, e_0 =-e_{-1}-e_1; \\
                    f_{-1} &= \frac{1}{(t_N-t_{N-2}+1)(t_N-t_{N-1}+1)}, \, f_{1} = \frac{1}{(t_N-t_{N-1}+2)(t_N-t_{N-1}+1)}, \, f_0 =-f_{-1}-f_1.
                \end{aligned}
            \right.\\
            \Rightarrow 6(e_{-1}\cdot a_{-1}+e_{0}\cdot a_{0}+e_{1}\cdot a_{1})=S^"(t_1)=S^"(t_N)=6(f_{-1}\cdot a_{N-2}+f_{0}\cdot a_{N-1}+f_{1}\cdot a_{N}).
        \end{align*}
        因此得到如下线性方程组 Ax = b ：
        \begin{align*}
            \begin{bmatrix}
                c_{-1} & c_0 & c_1 &  -d_{-1} & -d_0 & -d_1\\
                B_{-1,\mathbb{Z}}^3(t_1) & B_{0,\mathbb{Z}}^3(t_1) & B_{1,\mathbb{Z}}^3(t_1) & & &\\
                & \ddots & \ddots & \ddots & &\\
                & & B_{i-2,\mathbb{Z}}^3(t_i) & B_{i-1,\mathbb{Z}}^3(t_i) & B_{i,\mathbb{Z}}^3(t_i) & &\\
                & &  \ddots & \ddots & \ddots \\
                & & & B_{N-2,\mathbb{Z}}^3(t_{N}) & B_{N-1,\mathbb{Z}}^3(t_{N}) & B_{N,\mathbb{Z}}^3(t_{N}) \\
                e_{-1} & e_0 & e_1 &  -f_{-1} & -f_0 & -f_1
            \end{bmatrix}
            \begin{bmatrix}
                a_{-1} \\
                a_0 \\
                \vdots \\
                a_{i-1} \\
                \vdots \\
                a_{N-1} \\
                a_{N}
            \end{bmatrix}
            =
            \begin{bmatrix}
                0 \\
                f(t_1) \\
                \vdots \\
                f(t_{i}) \\
                \vdots \\
                f(t_{N}) \\
                0
            \end{bmatrix}
        \end{align*}
        \item 之后均同上。
    \end{enumerate}
\end{itemize}

\subparagraph*{ArbitraryOrderBSpline 类}
\texttt{ArbitraryOrderBSpline} 类继承自 \texttt{BSpline}，表示一个给定任意阶数、任意节点、任意基函数系数的任意阶 B 样条函数类，增加了一个成员函数并重写了评估函数：
\begin{itemize}
    \item $\texttt{double Bspline\_value(int i, int n, double x) const}$; 计算B样条的n次基函数在给定分段给定x处的函数值。
    \newline 
    算法流程：
    \begin{enumerate}
        \item 如果阶数 $n$ 为 0，则直接按照$B_i^0(x)$的定义返回基函数在 $x$ 处的值：
        \[
        B_i^0(x) =\\
        \begin{cases} 
        1, & x \in (t_{i-1}, t_i], \\
        0, & \text{otherwise}.
        \end{cases}    
        \]
        \item 否则，使用递归关系$B_i^{n+1}(x) = \frac{x - t_{i-1}}{t_{i+n} - t_{i-1}} B_i^n(x) + \frac{t_{i+n+1} - x}{t_{i+n+1} - t_i} B_{i+1}^n(x)$计算基函数值。
        \item 另外，计算过程中遇到超出knots范围的节点，继续用之前的方法进行人工延拓。
    \end{enumerate}

    \item $\texttt{virtual double evaluate(double x) const override}$; \newline
    算法流程：
    \begin{enumerate}
        \item 确保节点数量大于0，并且系数数量=节点数量+阶数 - 1。注意，构建样条时输入的系数成员变量coefficients不再是节点函数值，而是从 $2-n$ 到 $N$ 的基函数的系数，其中 $n$ 是样条的阶数。
        \item 找出 $x$ 所在的区间，确保 $x$ 在样条函数的定义域内。
        \item 初始化求和变量 sum 为 0， 对于每个基函数，计算其在 $x$ 处的值，并累加到 sum 中。
        \item 返回 sum 作为样条函数在 $x$ 处的值。
    \end{enumerate}
    
\end{itemize}


\subsection*{II-c. Curvefitting.h}
\texttt{Curvefitting.h} 是曲线拟合功能的核心头文件，提供了多种维度和参数类型的曲线拟合方法。该文件定义了以下函数：
\begin{center}
    \begin{tikzpicture}
        \node {Curvefitting.h}[grow'=right, scale=0.6, % 缩小整个树状图
        level distance=3cm, % 增加层间距
        sibling distance=1.5cm, % 减小节点间距
        level 1/.style={level distance=6cm, sibling distance=1.5cm}]
        child {node {Curve\_fitting\_2\_t}}
        child {node {Curve\_fitting\_2\_s}}    
        child [missing] {}
        child {node {Curve\_fitting\_Sphere\_t}}
        child {node {Curve\_fitting\_Sphere\_s}}
        child [missing] {}    
        child {node {plot\_exact\_2}}
        child {node {plot\_exact\_3}}
        ;
    \end{tikzpicture}
\end{center}

\subsubsection*{Curve\_fitting\_2\_t}
\texttt{Curve\_fitting\_2\_t} 函数用于在二维空间中进行基于参数 $t$ 的标准参数曲线拟合。它接受一个函数对象 $f$，分段数 $N$，参数范围 $[t\_min, t\_max]$，以及边界条件类型 $type$ 和一阶导数边界值 $mx1, mxN, my1, myN$。该函数的算法流程如下：

\begin{enumerate}
    \item 初始化分段间隔 $gap = \frac{t\_max - t\_min}{N}$。
    \item 创建节点向量 $\texttt{knots\_x}$ 和 $\texttt{knots\_y}$，以及系数向量 $\texttt{coefficients\_x}$ 和 $\texttt{coefficients\_y}$。
    \item 通过循环计算每个分段的函数值，并填充节点和系数向量。
    \item 根据边界条件类型 $type$，选择创建相应的 B 样条对象 $\texttt{Spline\_B\_x}$ 和 $\texttt{Spline\_y}$分别用于$x,y$坐标的样条插值。其中$type = 1$时，创建完全三次B样条对象，输入的$mx1, mxN, my1, myN$分别为$x,y$的一阶导数边界值；$type = 0$时，则创建周期三次B样条对象用于曲线拟合。
    \item 初始化用于存储拟合曲线值的向量 $\texttt{x\_values}$ 和 $\texttt{y\_values}$。
    \item 再次初始化间隔 $gap$ 用于生成拟合曲线的点。
    \item 循环计算每个拟合点的 $x$ 和 $y$ 值，并将它们添加到相应的向量中。
    \item 使用 matplotlib-cpp 库绘制拟合的样条曲线。
\end{enumerate}

\subsubsection*{Curve\_fitting\_2\_s}
\texttt{Curve\_fitting\_2\_s} 函数用于在二维空间中进行基于弦长的曲线拟合。接受的参数与\texttt{Curve\_fitting\_2\_t}一样，只在算法流程上，用于曲线拟合的样条节点略有不同：
\begin{enumerate}
    \item 仍然初始化分段间隔 $gap = \frac{t\_max - t\_min}{N}$，并创建相关节点、系数向量。
    \item 初始化参数 $t = t\_min$ 和弧长 $s = 0$。
    \item 循环计算每个$t$分段处的函数值以填充系数向量，并更新对应的累积弦长 $s$ 以填充节点向量。
    \item 根据边界条件类型 $type$，创建相应的 B 样条对象 $\texttt{Spline\_B\_x}$ 和 $\texttt{Spline\_B\_y}$。
    \item 初始化用于存储拟合曲线值的向量 $\texttt{x\_values}$ 和 $\texttt{y\_values}$。
    \item 计算拟合曲线关于总弦长$s_{max}$的间隔 $gap = \frac{s\_max}{M}$，其中 $M$ 是拟合曲线的分段数。
    \item 循环计算每个拟合点的 $x$ 和 $y$ 值，并将它们添加到相应的向量中。
    \item 使用 matplotlib-cpp 库绘制拟合的样条曲线。
\end{enumerate}

\subsubsection*{Curve\_fitting\_Sphere\_t}
\texttt{Curve\_fitting\_Sphere\_t} 函数用于在球面上进行基于参数 $t$ 的标准参数曲线拟合。与\texttt{Curve\_fitting\_2\_t}相比，它额外接受一个球面半径 $R$ ，并且它接受的函数对象 $f$ 所输出的函数值不再是点在平面上的$(x(t),y(t))$坐标，而是点在球面上的经纬度坐标$(u(t),v(t))$。基于此，该函数的算法流程如下：

\begin{enumerate}
    \item 首先对经纬度坐标u,v进行平面上的标准参数曲线拟合。
    \item 对于每个拟合点，根据得到的u,v拟合结果，按照如下公式转换，得到拟合点的三维坐标x,y,z：
    \[ \left\{ \begin{array}{l}
    x = R\sin u \cos v, \\
    y = R\sin u \sin v, \\
    z = R\cos u,
    \end{array} \right. \]
    \item 使用 matplotlib-cpp 库根据(x,y,z)的向量值绘制样条曲线。
\end{enumerate}

\subsubsection*{Curve\_fitting\_Sphere\_s}
\texttt{Curve\_fitting\_Sphere\_s} 函数用于在球面上进行基于弦长的曲线拟合。它与\texttt{Curve\_fitting\_Sphere\_t}完全类似，只是在对经纬度坐标u,v进行平面上的曲线拟合时，采用了\texttt{Curve\_fitting\_2\_s}中的基于弦长的曲线拟合方法。

\subsubsection*{plot\_exact\_2}
\texttt{plot\_exact\_2} 函数用于绘制二维空间中的真实曲线。它接受一个函数对象 $f$ 和参数范围 $[t1, t2]$，在绘制曲线上的点时，直接调用函数$f$计算出真实的函数值$(x(t),y(t))$。

\subsubsection*{plot\_exact\_3}
\texttt{plot\_exact\_3} 函数用于绘制三维空间中的真实曲线。它接受一个三维函数对象 $f$ 和参数范围 $[t1, t2]$，在绘制曲线上的点时，直接调用函数$f$计算出真实的函数值$(x(t),y(t),z(t))$。

\section*{III. 总结与感悟}
\subsection*{反思总结}
\begin{itemize}
    \item 在写设计报告的时候回头看看自己写下的程序，发现了很多不足之处和有待改进的地方。
    \item 总的来说，在写下第一行代码之前，虽然也在纸上先进行了一个大概的架构设计，但并没能很全面地综合考虑到各种因素来搭建一个成熟的框架，导致整个项目结构仍然比较幼稚和愚蠢。
    \item 另外，在项目编写后期，因为战线拖得太久了，已经不大想去改动此前写好的可以实现功能但不大聪明的代码，导致代码之间存在一些不必要的重复或者前后不统一等问题。
    \item 比如说在设计样条函数类的继承关系时，只是很单纯地按照直觉划分了三层，后续也没有很好地利用继承关系来复用代码；
    \item 在曲线拟合函数中，本来可以通过调用前一种已经写好的拟合函数来实现另一种拟合方法，但秉持着“不报错能运行的就是好代码”的原则，我选择了简单粗暴的复制粘贴......
    \item 这些问题鉴于时间关系没有办法再一一尝试解决，留待未来有机会再加以改进吧。
\end{itemize}

\subsection*{一些感想}
\begin{itemize}
    \item 对我来说，这是很有纪念意义的一次作业。
    \item 这应该是我第一次持续地花费那么多时间和精力在一个东西上，从项目作业布置开始，到现在是12.4的上午10点，前前后后断断续续地肝了25天，也是狠狠体验了一把码农的生活。
    \item 最大的收获应该是极大增加了我对敲代码和debug的信心和耐心！在此之前我还是一个编程全靠kimi发力、一有报错就烦躁地想重开的小笨蛋，第一天看到密密麻麻的作业要求时，其实很难想象到自己真的可以手搓出几千行代码来完成这个看着就很复杂的任务。
    \item 但在ddl的push下我还是硬着头皮开始干了。尝试放下眼高手低的完美主义心态，把看上去庞大繁杂的任务分割成一个个小的部分，然后每天干掉一点点，渐渐地就发现，轻舟已过万重山啦。
\end{itemize}
% ===============================================

\end{document}